package com.yun.algorithmproblem.leetcode;

import com.yun.datastructure.linear.list.linkedlist.ListNode;

public class Leetcode86 {
    public ListNode partition(ListNode head, int x) {
        ListNode sentinel=new ListNode(-1,head);
        ListNode less=sentinel;
        ListNode more;
        ListNode p=head;
        while (p!=null&&p.val<x){
            less=p;
            p=p.next;
        }
        if(p==null){
            return sentinel.next;
        }
        more=p;
        while (p.next!=null){
            if(p.next.val<x){
                ListNode q=p.next.next;
                p.next.next=more;
                less.next=p.next;
                less=less.next;
                p.next=q;
            }else {
                p=p.next;
            }
        }
        return sentinel.next;
    }

    public static void main(String[] args) {
        //ListNode head=new ListNode(1,new ListNode(4,new ListNode(3,
                //new ListNode(2,new ListNode(5,new ListNode(2))))));
        ListNode head=new ListNode(1);
        int x=2;
        Leetcode86 test=new Leetcode86();
        System.out.println(test.partition(head, x));
    }
}
